Searching Analysis¶
Consider a finite collection of element. Finding whether element exsists in collection is known as Searching. Following are some of the comparision based Searching Algorithms.
- Linear Search
- Binary Search
Before looking at the analysis part, we shall examine the Language in built methods to searching
The in
operator and list.index()
¶
We have already seen the in
operator in several contexts. Let’s see
the working of in
operator again
In [1]:
x = list(range(10))
In [2]:
x
Out[2]:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
In [3]:
6 in x
Out[3]:
True
In [4]:
100 in x
Out[4]:
False
In [5]:
x.index(6)
Out[5]:
6
In [6]:
x.index(100)
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
<ipython-input-6-0f87238c301b> in <module>()
----> 1 x.index(100)
ValueError: 100 is not in list
Standard import
statement¶
In [16]:
from openanalysis.searching import SearchingAlgorithm,SearchAnalyzer
%matplotlib inline
%config InlineBackend.figure_formats={"svg", "pdf"}
SearchingAlgorithm
is the base class providing the standards to
implement searching algorithms, SearchAnalyzer
analyses the
algorithm
SearchingAlgorithm
class¶
Any searching algorithm, which has to be implemented, has to be derived from this class. Now we shall see data members and member functions of this class.
Data Members¶
name
- Name of the Searching Algorithmcount
- Holds the number of basic operations performed
Member Functions¶
__init__(self, name):
- Initializes algorithm with aname
search(self, array, key):
_ The base searching function. Setscount
to 0.array
is 1Dnumpy
array,key
is the key of element to be found out
An example …. Binary Search¶
Now we shall implement the class BinarySearch
In [17]:
class BinarySearch(SearchingAlgorithm): # Inheriting
def __init__(self):
SearchingAlgorithm.__init__(self, "Binary Search") # Initailizing with name
def search(self, arr, key):
SearchingAlgorithm.search(self, arr, key) # call base class search
low, high = 0, arr.size - 1
while low <= high:
mid = int((low + high) / 2)
self.count += 1 # Increment for each basic operation performed
if arr[mid] == key:
return True
elif arr[mid] < key:
low = mid + 1
else:
high = mid - 1
return False
SearchAnalyzer
class¶
This class provides the visualization and analysis methods. Let’s see its methods in detail
__init__(self, searcher):
Initializes visualizer with a Searching Algorithm.searcher
is a class, which is derived fromSearchingAlgorithm
analyze(self, maxpts=1000):
- Plots the running time of searching algorithm by searching in 3 cases
- Key is the first element, Key is the last element, Key at random index
- Analysis is done by inputting sorted integer arrays with size
staring from 100, and varying upto
maxpts
in the steps of 100, and counting the number of basic operations maxpts
Upper bound on size of elements chosen for analysing efficiency
In [18]:
bin_visualizer = SearchAnalyzer(BinarySearch)
<matplotlib.figure.Figure at 0x7ff57329b978>
In [19]:
bin_visualizer.analyze(progress=False)
Please wait while analyzing Binary Search Algorithm
Note performance in all cases
compare(algs)
¶
algs
is a list of classes derived from SearchingAlgorithm
. It
performs tests and plots the bar graph comapring the number of basic
operations performed by each algorithm.